import java.util.*;

public class TestBinaryTree {
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;//就是根节点
    }

    //二叉树遍历
    public static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    // 注意类名必须为 Main, 不要有任何 package xxx 信息
    public class Main {
        public static int i = 0;

        public static TreeNode cretateTree(String str) {
            TreeNode root = null;
            if (str.charAt(i) != '#') {
                root = new TreeNode(str.charAt(i));
                i++;
                root.left = cretateTree(str);
                root.right = cretateTree(str);
            } else {
                i++;
            }
            return root;
        }

        public static void inorder(TreeNode root) {
            if (root == null) return;
            inorder(root.left);
            System.out.print(root.val + " ");
            inorder(root.right);
        }

    }

    //二叉树前序非递归遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            cur = stack.pop();
            cur = cur.right;
        }
        return list;
    }

    //二叉树后序非递归遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) return list;
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.empty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            // if(top.right == null || top.right == prev){
            //     list.add(top.val);
            //     stack.pop();
            //     prev = top;
            // }else{
            //     cur = top.right;
            // }
            if (top.right != null && top.right != prev) {
                cur = top.right;
            } else {
                list.add(top.val);
                stack.pop();
                prev = top;
            }
        }
        return list;
    }

    //二叉树中序非递归遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if (root == null) return list;
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        }
        return list;
    }
    //二叉树的层序遍历II

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> ret = new LinkedList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while (size > 0) {
                cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.addFirst(list);
        }
        return ret;
    }
    //两个节点的最近公共祖先
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (p == root || q == root) {
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left, p, q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p, q);
        if (leftTree == null && rightTree == null) {
            return null;
        }
        if (leftTree != null && rightTree == null) {
            return leftTree;
        }
        if (leftTree == null && rightTree != null) {
            return rightTree;
        }
        return root;
    }
    //非递归
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        Stack<TreeNode> stack1 = new Stack<>();
//        Stack<TreeNode> stack2 = new Stack<>();
//        getNodePath(root,p,stack1);
//        getNodePath(root,q,stack2);
//        int i = stack1.size();
//        int j = stack2.size();
//        while(!stack1.empty() && !stack2.empty()){
//            if(i > j){
//                stack1.pop();
//                i--;
//            }else if(i < j){
//                stack2.pop();
//                j--;
//            }else{
//                if(stack1.peek() == stack2.peek()){
//                    return stack1.peek();
//                }else{
//                    i--;
//                    j--;
//                    stack1.pop();
//                    stack2.pop();
//                }
//            }
//        }
//        return null;
//    }
//    private boolean getNodePath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
//        if(null == root || null == node){
//            return false;
//        }
//        stack.push(root);
//        if(root == node){
//            return true;
//        }
//        if(getNodePath(root.left,node,stack) || getNodePath(root.right,node,stack)){
//            return true;
//        }
//        stack.pop();
//        return false;
//    }
    //二叉树的分层遍历
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode cur = root;
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while (size > 0) {
                cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    //根据二叉树创建字符串
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    public String tree2str(TreeNode root) {
        if (root == null) {
            return "";
        }
        if (root.left == null && root.right == null) {
            return Integer.toString(root.val);
        }
        if (root.right == null) {
            return new StringBuilder().append(root.val).append('(').append(tree2str(root.left)).append(')').toString();
        }
        return new StringBuilder().append(root.val).append('(').append(tree2str(root.left)).append(")(").
                append(tree2str(root.right)).append(')').toString();
    }
}
